package pacBioSimple;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


import pacBiopackage.Pair;

import tools.kmer.KmerSet_binary;
import tools.sequences.sequenceUtils;

public class PacBioBridgeMainObject {
	private List<Integer> seeds= null;
	private CodingTable table = null;
	private Random generator = new Random();
	private StringBuilder readSequence=null;
	private KmerSet_binary ks = null;
//	private Logger log = Logger.getLogger(PacBioKmerAlgoMain.class.getName());
	private int repVal = 70;
	private KKmerList kmerVector =null;
	private Entropy<?> entropy = null;
	private double cutoff=0.5;
	private int counter=0;
	private boolean contamination = false;
	private List<Integer> contaminationBreakPoints = null;
	private boolean linker=false;
	
	
	
	
	
	public List<Integer> getContaminationBreakPoints() {
		return contaminationBreakPoints;
	}

	public void setContaminationBreakPoints(List<Integer> contaminationBreakPoints) {
		this.contaminationBreakPoints = contaminationBreakPoints;
	}

	public boolean isContamination() {
		return contamination;
	}

	public void setContamination(boolean contamination) {
		this.contamination = contamination;
	}

	public boolean getLinker()
	{
		return this.linker;
	}

	public int getCounter() {
		return counter;
	}


	public void setCounter(int counter) {
		this.counter = counter;
	}


	public PacBioBridgeMainObject(List<Integer>seeds, CodingTable table,StringBuilder readSequence,KmerSet_binary ks,int kmer_count_limt,KKmerList kmerVector)
	{
		this.seeds=seeds;
		this.table=table;
		this.readSequence=readSequence;
		this.ks=ks;
		this.repVal=kmer_count_limt;
		this.kmerVector=kmerVector;
		List<Character> alphabet = new ArrayList<Character>();
		alphabet.add('A');
		alphabet.add('C');
		alphabet.add('G');
		alphabet.add('T');
		entropy = new Entropy<Character>(alphabet);
		
	}
	
	
	public void firstSeedReverse(List<Path>candidatesList,List<Boolean>signal)
	{
		MyUtil.logging("first seed");
		MyUtil.logging(String.valueOf(kmerVector.getKmerSize()));
		//	System.out.println("first seed");
		//	System.out.println(kmerVector.getKmerSize());
		
		Path newCandidatesPathes = new Path();
		StringBuilder seed1 = new StringBuilder(readSequence.substring(seeds.get(0),seeds.get(0)+ks.getKmerSize()));
		seed1=sequenceUtils.reverseComplement2(seed1);
		PacBioSeedBridgingReduceExtend temp = new PacBioSeedBridgingReduceExtend(seeds.get(0),seeds.get(0),table, ks, true,repVal,kmerVector,readSequence,newCandidatesPathes);
		//PacBioSeedBridgingKmer temp = new PacBioSeedBridgingKmer(seeds.get(0),seeds.get(0),table, ks, true,repVal,kmerVector,readSequence,newCandidatesPathes);
		//PacBioSeedBridgingSimple temp = new PacBioSeedBridgingSimple(seed1,seeds.get(0),table, ks, true,repVal,newCandidatesPathes);
		temp.run();
		
		temp=null;
		//do the alignment	
		//we need the pacBio sequence
		String pacBioSequence = readSequence.substring(0,seeds.get(0)+ks.getKmerSize());
		newCandidatesPathes.setToBeAlign(pacBioSequence);
		if(newCandidatesPathes.getRepeatsEndedpaths().size()!=0)
		{
			List<String>shorterPath = new ArrayList<String>();
			int end=seeds.get(0)+ks.getKmerSize();
			for(int i=0; i < newCandidatesPathes.getRepeatsEndedpaths().size();++i)
			{
				if(end-newCandidatesPathes.getRepeatsEndedpaths().get(i).length()<0)
				{
					shorterPath.add(readSequence.substring(0,seeds.get(0)+ks.getKmerSize()));
				}
				else
				shorterPath.add(readSequence.substring(end-newCandidatesPathes.getRepeatsEndedpaths().get(i).length(),seeds.get(0)+ks.getKmerSize()));
			}
			newCandidatesPathes.setStoppedTemplate(shorterPath);
		}
		signal.add(false);
		//if candidatepath is not valid, 
		if(newCandidatesPathes.getFullpaths().get(0).length()<seed1.length() && newCandidatesPathes.getRepeatsEndedpaths().size()==0)
		{
			List<StringBuilder>temp_ = new ArrayList<StringBuilder>();
			temp_.add(seed1);
			newCandidatesPathes.setRepeatsEndedpaths(temp_);
			List<String>shorterPath = new ArrayList<String>();
			shorterPath.add(readSequence.substring(0,seeds.get(0)+ks.getKmerSize()));
			newCandidatesPathes.setStoppedTemplate(shorterPath);
		}
		MyUtil.logging("first Seed output");
		MyUtil.logging(newCandidatesPathes.toString());
		
		//	System.out.println("first Seed output");
		//	System.out.println(newCandidatesPathes.toString());
				
		newCandidatesPathes.setBegin(true);
		candidatesList.add(newCandidatesPathes);		
	}
	
	public void lastSeeds(List<Path>candidatesList,List<Boolean>signal)
	{
		//List<StringBuilder>candidate = new ArrayList<StringBuilder>();
		MyUtil.logging("last seeds");
		//System.out.println("last seeds");
		Path newCandidatesPathes = new Path();
		StringBuilder seed1 = new StringBuilder(readSequence.substring(seeds.get(seeds.size()-1),seeds.get(seeds.size()-1)+ks.getKmerSize()));
		//System.out.println(seed1 + " "+seed1.length());
		PacBioSeedBridgingReduceExtend temp = new PacBioSeedBridgingReduceExtend(seeds.get(seeds.size()-1),readSequence.length()-seeds.get(seeds.size()-1),table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		//PacBioSeedBridgingKmer temp = new PacBioSeedBridgingKmer(seeds.get(seeds.size()-1),readSequence.length()-seeds.get(seeds.size()-1),table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		temp.run();
		temp=null;
		String pacBioSequence = readSequence.substring(seeds.get(seeds.size()-1),readSequence.length());
		//System.out.println("pacBioSequence "+ pacBioSequence);
		newCandidatesPathes.setToBeAlign(pacBioSequence);
		MyUtil.logging(newCandidatesPathes.toString());
		//System.out.println(newCandidatesPathes.toString());
		//System.out.println("seedsSize "+seeds.get(seeds.size()-1));
		//System.out.println("getRepeatsEndedPaths "+ newCandidatesPathes.getRepeatsEndedpaths().toString());
		if(newCandidatesPathes.getRepeatsEndedpaths().size()!=0)
		{
			if(!newCandidatesPathes.getRepeatsEndedpaths().get(0).equals("") && newCandidatesPathes.getRepeatsEndedpaths().get(0).length()<ks.getKmerSize())
			{
				MyUtil.logging("test "+ seed1 + " length "+ seed1.length());
				//System.out.println("test "+ seed1 + " length "+ seed1.length());
				List<StringBuilder>temp_ = new ArrayList<StringBuilder>();
				temp_.add(seed1);
				newCandidatesPathes.setRepeatsEndedpaths(temp_);
			}
			//now we have to generate a template sequence from pacBio
			
			List<String>shorterPath = new ArrayList<String>();
			MyUtil.logging("sequence length "+readSequence.length() + " seed pos "+ seeds.get(seeds.size()-1));
			//System.out.println("sequence length "+readSequence.length() + " seed pos "+ seeds.get(seeds.size()-1));
			for(int i=0; i < newCandidatesPathes.getRepeatsEndedpaths().size();++i)
			{
				int length_val = newCandidatesPathes.getRepeatsEndedpaths().get(i).length()-ks.getKmerSize();
				MyUtil.logging(String.valueOf(length_val));
				//System.out.println(length_val);
				if(length_val<=0)
				shorterPath.add(readSequence.substring(seeds.get(seeds.size()-1),seeds.get(seeds.size()-1)+ks.getKmerSize()));
				else if(length_val+seeds.get(seeds.size()-1)>=readSequence.length())
				{
					shorterPath.add(readSequence.substring(seeds.size()-1,readSequence.length()));
				}
				else
				{
					shorterPath.add(readSequence.substring(seeds.get(seeds.size()-1),seeds.get(seeds.size()-1)+length_val));
				}
			}
			newCandidatesPathes.setStoppedTemplate(shorterPath);
		}
		//System.out.println("length_ "+newCandidatesPathes.getFullpaths().size() +" "+newCandidatesPathes.getRepeatsEndedpaths().size()+"\n");
		//the case if we have not a valid candidate path, 
		
		if(newCandidatesPathes.getFullpaths().get(0).length()<seed1.length() && newCandidatesPathes.getRepeatsEndedpaths().size()==0)
		{
			List<StringBuilder>temp_ = new ArrayList<StringBuilder>();
			temp_.add(seed1);
			newCandidatesPathes.setRepeatsEndedpaths(temp_);
			List<String>shorterPath = new ArrayList<String>();
			shorterPath.add(readSequence.substring(seeds.size()-1,readSequence.length()));
			
			newCandidatesPathes.setStoppedTemplate(shorterPath);
		}
		signal.add(false);
		MyUtil.logging("last Seed output");
		MyUtil.logging(newCandidatesPathes.toString());
		//System.out.println("last Seed output");
		//System.out.println(newCandidatesPathes.toString());
		newCandidatesPathes.setEnd(true);
		candidatesList.add(newCandidatesPathes);
	}
	
	//vorerst nur einen, falls mehr -> alignment..
	protected StringBuilder longCandidate(Path newCandidatePathes,int distance)
	{
		List<StringBuilder>temp = new ArrayList<StringBuilder>();
		for(int i=0; i<newCandidatePathes.getRepeatsEndedpaths().size();++i)
		{
			int size =newCandidatePathes.getRepeatsEndedpaths().get(i).length();
			if(temp.size()==0  && size >=distance)
			{
				temp.add(newCandidatePathes.getRepeatsEndedpaths().get(i));
			}
			else
			{
				if(temp.get(temp.size()-1).length()<size)
				{
					temp.clear();
					temp.add(newCandidatePathes.getRepeatsEndedpaths().get(i));
				}
				else if(temp.get(temp.size()-1).length()==size)
				{
					temp.add(newCandidatePathes.getRepeatsEndedpaths().get(i));
				}
			}
		}
		if(temp.size()==0)		
		return null;
		else
		{
			if(temp.size()>1)
			{
				return temp.get(generator.nextInt(temp.size()));
			}
			else
			{
				return temp.get(0);
			}
		}
	}
	
	public void inbetweenSeed2(List<Path>candidatesList,int i,List<Boolean>signal)
	{
		MyUtil.logging("inbetween "+ i);
		//System.out.println("inbetween "+ i);
		Path newCandidatesPathes = new Path();
		StringBuilder seed1 = new StringBuilder(readSequence.substring(seeds.get(i),seeds.get(i)+ks.getKmerSize()));
		StringBuilder seed2 = new StringBuilder(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
		int distance = seeds.get(i+1)+ks.getKmerSize()-seeds.get(i)+ks.getKmerSize();
		//System.out.println("seeds " +seeds.get(i+1));
		PacBioSeedBridgingReduceExtend temp = new PacBioSeedBridgingReduceExtend(seeds.get(i), seeds.get(i+1), distance, table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		//PacBioSeedBridgingKmer temp = new PacBioSeedBridgingKmer(seeds.get(i), seeds.get(i+1), distance, table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		temp.run();
		temp=null;
		StringBuilder longCandidate =longCandidate(newCandidatesPathes, distance);
		//here we have to think about
		String pacBioSequence = null; 
		if(longCandidate!=null)
		{
			//newCandidatesPathes = new Path();
			double a = entropy.calcEntropy(seed1.toString());
			double b = entropy.calcEntropy(seed2.toString());
			
			if(a>b && b<=cutoff)
			{
				seeds.remove(i+1);
				//restart extension
				//build up new PacBioSeedBridging
				if(i+1>=seeds.size())
				{
					lastSeeds(candidatesList,signal);
				}
				else
				{
					//seed2 = new StringBuilder(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
					distance = seeds.get(i+1)+ks.getKmerSize()-seeds.get(i)+longCandidate.length();
					if(distance>0)						
					{
						//has to be chaged... to expensive in ct
						inbetweenSeed2(candidatesList,i, signal);
						//temp = new PacBioSeedBridgingReduceExtend(longCandidate, seed2,seeds.get(i),seeds.get(i+1), distance, table, ks, false, distance, kmerVector, readSequence, newCandidatesPathes);
						//temp.run();
					}
					else
					{
						MyUtil.logging("distance <0");
						//System.out.print("distance <0");
						System.exit(1);
					}
				}
			}
			else
			{
				if(a<b && b>cutoff)
				{
					MyUtil.logging("b cutoff is greater than a" + a+" "+b);
					System.out.println("b cutoff is greater than a" + a+" "+b);
					System.exit(1);
				}
			}
		}
		else
		{
			pacBioSequence=readSequence.substring(seeds.get(i),seeds.get(i+1)+ks.getKmerSize());
			newCandidatesPathes.setToBeAlign(pacBioSequence);
			
			if(newCandidatesPathes.getRepeatsEndedpaths().size()!=0)
			{
				List<String>shorterPath = new ArrayList<String>();
				for(int j=0; j < newCandidatesPathes.getRepeatsEndedpaths().size();++j)
				{
					if(seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()>= readSequence.length())
					{
						MyUtil.logging("readlength "+readSequence.length()+" requiered length: "+ (seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()) + " "+seeds.get(i)+" "+newCandidatesPathes.getRepeatsEndedpaths().get(j).length());
						//System.out.println("readlength "+readSequence.length()+" requiered length: "+ (seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()) + " "+seeds.get(i)+" "+newCandidatesPathes.getRepeatsEndedpaths().get(j).length());
						shorterPath.add(readSequence.substring(seeds.get(i),readSequence.length()));
					}
					else
					shorterPath.add(readSequence.substring(seeds.get(i),seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()));
				}
				newCandidatesPathes.setStoppedTemplate(shorterPath);
				
				newCandidatesPathes.setType(true);
			}
			MyUtil.logging(newCandidatesPathes.toString());
			MyUtil.logging("type active " + newCandidatesPathes.getType());
			//System.out.println(newCandidatesPathes.toString());
			//System.out.println("type active " + newCandidatesPathes.getType());
			if(newCandidatesPathes.getType())
			{ 
				
				//seed1=sequenceUtils.reverseComplement2(seed1);
				//seed2=sequenceUtils.reverseComplement2(seed2);
				inbetweenReverse(newCandidatesPathes, distance, candidatesList, signal);
			}
			else
			{
				List<StringBuilder> onlykmer = new ArrayList<StringBuilder>();
				onlykmer.add(seed2);
				newCandidatesPathes.setRepeatsEndedpaths_r(onlykmer);
				onlykmer=null;
				List<String>shorterPath = new ArrayList<String>();
				shorterPath.add(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
				newCandidatesPathes.setStoppedTemplate_R(shorterPath);
			}
			
	/*		if(!newCandidatesPathes.getType() && newCandidatesPathes.getFullpaths().size()==1 && newCandidatesPathes.getFullpaths().get(0).toString()=="" && newCandidatesPathes.getRepeatsEndedpaths().size()==1 && newCandidatesPathes.getRepeatsEndedpaths().get(0).toString()=="" )
			{
				
			}
			*/
			signal.add(false);
			MyUtil.logging("inbetween output");
			MyUtil.logging(newCandidatesPathes.toString());
			//System.out.println("inbetween output");
			//System.out.println(newCandidatesPathes.toString());
			if(!newCandidatesPathes.isBegin() && !newCandidatesPathes.isEnd())
			candidatesList.add(newCandidatesPathes);
		}
	}
	
	protected void inbetweenReverse(Path newCandidatesPathes ,int i,List<Path>candidatesList,List<Boolean>signal)
	{
		Path newReversedPath = new Path();
		int distance = seeds.get(i+1)-seeds.get(i);
		PacBioSeedBridgingReduceExtend temp = new PacBioSeedBridgingReduceExtend(seeds.get(i+1), seeds.get(i), distance, table, ks,true,repVal,kmerVector,readSequence, newReversedPath);
		//temp = new PacBioSeedBridgingKmer(seeds.get(i+1), seeds.get(i), distance, table, ks,true,repVal,kmerVector,readSequence, newReversedPath);
		temp.run();
		//System.out.println("right Seeds to left "+newReversedPath.toString());
		temp = null;
		StringBuilder longCandidate =longCandidate(newCandidatesPathes, distance);
		
		if(longCandidate!=null)
		{
			double a = entropy.calcEntropy(readSequence.substring(seeds.get(i),seeds.get(i)+ks.getKmerSize()));
			double b = entropy.calcEntropy(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
			
			if(a<b && a<=cutoff)
			{
				seeds.remove(i-1);
				candidatesList.remove(candidatesList.size()-1);
				--i;
				//restart extension
				//build up new PacBioSeedBridging
				if(i-1<=0)
				{
					firstSeedReverse(candidatesList, signal);
				}
				else
				{
					//seed2 = new StringBuilder(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
					distance = seeds.get(i+1)-longCandidate.length()-seeds.get(i);
					if(distance>0)						
					{
						inbetweenReverse(newCandidatesPathes,i,candidatesList,signal);
						//has to be chaged... to expensive in ct
						//temp = new PacBioSeedBridgingReduceExtend(longCandidate, seed2,seeds.get(i),seeds.get(i+1), distance, table, ks, false, distance, kmerVector, readSequence, newCandidatesPathes);
						//temp.run();
					}
					else
					{
						System.out.print("ARG kommt doch vor distance <0");
						System.exit(1);
					}
				}
			}
			else
			{
				if(a<b && b>cutoff)
				{
					System.out.println("b cutoff is greater than a" + a+" "+b);
					System.exit(1);
				}
			}
		}
		else
		{
			if(newReversedPath.getRepeatsEndedpaths().size()!=0)
			{
				newCandidatesPathes.setRepeatsEndedpaths_r(newReversedPath.getRepeatsEndedpaths());
				
				List<String>shorterPath = new ArrayList<String>();
				int end=seeds.get(i+1)+ks.getKmerSize();
				//System.out.println(end);
				for(int j=0; j < newReversedPath.getRepeatsEndedpaths().size();++j)
				{
					//System.out.println(j+" "+newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()+" "+ (end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()) );
					//System.out.println(seeds.get(i+1));
					if(end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()<0)
					{
						shorterPath.add(readSequence.substring(seeds.get(i),seeds.get(i+1)+ks.getKmerSize()));
					}
					else
					{
						shorterPath.add(readSequence.substring(end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length(),seeds.get(i+1)+ks.getKmerSize()));
					}
				}	
				newCandidatesPathes.setStoppedTemplate_R(shorterPath);
			}
		}
	}
	
	

	public void inbetweenSeed( List<Path>candidatesList,int i,List<Boolean>signal)
	{
		//System.out.println("inbetween");
		Path newCandidatesPathes = new Path();
		StringBuilder seed1 = new StringBuilder(readSequence.substring(seeds.get(i),seeds.get(i)+ks.getKmerSize()));
		StringBuilder seed2 = new StringBuilder(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
		int distance = seeds.get(i+1)-seeds.get(i)+ks.getKmerSize();
		//System.out.println("seeds " +seeds.get(i)+" "+seeds.get(i+1));
		PacBioSeedBridgingReduceExtend temp = new PacBioSeedBridgingReduceExtend(seeds.get(i), seeds.get(i+1), distance, table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		//PacBioSeedBridgingKmer temp = new PacBioSeedBridgingKmer(seeds.get(i), seeds.get(i+1), distance, table, ks,false,repVal,kmerVector,readSequence,newCandidatesPathes);
		temp.run();
		temp=null;
		String pacBioSequence = readSequence.substring(seeds.get(i),seeds.get(i+1)+ks.getKmerSize());
		newCandidatesPathes.setToBeAlign(pacBioSequence);
		if(newCandidatesPathes.getRepeatsEndedpaths().size()!=0)
		{
			List<String>shorterPath = new ArrayList<String>();
			for(int j=0; j < newCandidatesPathes.getRepeatsEndedpaths().size();++j)
			{
				if(seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()>= readSequence.length())
				{
					//System.out.println("readlength "+readSequence.length()+" requiered length: "+ (seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()) + " "+seeds.get(i)+" "+newCandidatesPathes.getRepeatsEndedpaths().get(j).length());
					shorterPath.add(readSequence.substring(seeds.get(i),readSequence.length()));
				}
				else
				shorterPath.add(readSequence.substring(seeds.get(i),seeds.get(i)+newCandidatesPathes.getRepeatsEndedpaths().get(j).length()));
			}
			newCandidatesPathes.setStoppedTemplate(shorterPath);
			
			newCandidatesPathes.setType(true);
		}
		//System.out.println("length_ "+newCandidatesPathes.getFullpaths().size() +" "+newCandidatesPathes.getRepeatsEndedpaths().size()+" "+newCandidatesPathes.getFullpaths().get(0).indexOf("")+"\n");
		if(newCandidatesPathes.getFullpaths().get(0).length()<seed1.length()&& newCandidatesPathes.getRepeatsEndedpaths().size()==0)
		{
			newCandidatesPathes.setType(true);
		}
		
		//System.out.println(newCandidatesPathes.toString());
		//System.out.println("type active " + newCandidatesPathes.getType());
		boolean linker =false;
		if(newCandidatesPathes.getType())
		{ 
			Path newReversedPath = new Path();
			//seed1=sequenceUtils.reverseComplement2(seed1);
			//seed2=sequenceUtils.reverseComplement2(seed2);
			temp = new PacBioSeedBridgingReduceExtend(seeds.get(i+1), seeds.get(i), distance, table, ks,true,repVal,kmerVector,readSequence, newReversedPath);
			//temp = new PacBioSeedBridgingKmer(seeds.get(i+1), seeds.get(i), distance, table, ks,true,repVal,kmerVector,readSequence, newReversedPath);
			temp.run();
			
			//System.out.println("right Seeds to left "+newReversedPath.toString());
			
			if(newReversedPath.getRepeatsEndedpaths().size()!=0)
			{
				newCandidatesPathes.setRepeatsEndedpaths_r(newReversedPath.getRepeatsEndedpaths());
				
				List<String>shorterPath = new ArrayList<String>();
				int end=seeds.get(i+1)+ks.getKmerSize();
				//System.out.println(end);
				for(int j=0; j < newReversedPath.getRepeatsEndedpaths().size();++j)
				{
					//System.out.println(j+" "+newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()+" "+ (end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()) );
					//System.out.println(seeds.get(i+1));
					if(end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length()<0)
					{
						shorterPath.add(readSequence.substring(seeds.get(i),seeds.get(i+1)+ks.getKmerSize()));
					}
					else
					{
						shorterPath.add(readSequence.substring(end-newCandidatesPathes.getRepeatsEndedpaths_r().get(j).length(),seeds.get(i+1)+ks.getKmerSize()));
					}
				}	
				newCandidatesPathes.setStoppedTemplate_R(shorterPath);
				//System.out.println("before checking linker");
				//System.out.println(newCandidatesPathes.toString());
				linker=checkForLinker(newCandidatesPathes,i,seed1, seed2,candidatesList,distance);				
			}
			else
			{
				List<StringBuilder> onlykmer = new ArrayList<StringBuilder>();
				onlykmer.add(seed2);
				newCandidatesPathes.setRepeatsEndedpaths_r(onlykmer);
				onlykmer=null;
				List<String>shorterPath = new ArrayList<String>();
				shorterPath.add(readSequence.substring(seeds.get(i+1),seeds.get(i+1)+ks.getKmerSize()));
				newCandidatesPathes.setStoppedTemplate_R(shorterPath);
			}
		}
		if(!linker)
		{
			signal.add(false);
//			System.out.println("inbetween output");
//			System.out.println(newCandidatesPathes.toString());
			candidatesList.add(newCandidatesPathes);
		}
	}

	private int checkInverseSeed(StringBuilder seed, StringBuilder patchSequence)
	{
		int found =patchSequence.indexOf(sequenceUtils.reverseComplement2(seed).toString());
		return found;
	}
	
	
	private boolean checkForLinker(Path candiate,int pos,StringBuilder seed1, StringBuilder seed2,List<Path>candidatesList,int distance)
	{
		//left to right
		//System.out.println("check for linker sequence ");
		//System.out.println(candiate.toString());
		
		boolean found_linker_1 =false;
		boolean found_linker_2 =false;
		for(int i=0; i <candiate.getRepeatsEndedpaths().size();++i)
		{
			int test = checkInverseSeed(seed2, candiate.getRepeatsEndedpaths().get(i));
			if(test!=-1)
			{
				found_linker_1=true;
				break;
			}
		}
		for(int i=0; i <candiate.getRepeatsEndedpaths_r().size();++i)
			{
				int test = checkInverseSeed(seed1, candiate.getRepeatsEndedpaths_r().get(i));
				if(test!=-1)
				{
					found_linker_2=true;
					break;
				}
			}
		
		if(found_linker_1 && !found_linker_2 || !found_linker_1 && found_linker_2)
		{
			this.linker=true;
			MyUtil.logging("linker where found at: "+ seeds.get(pos) +" "+seeds.get(pos+1));
			//System.out.println("linker where found at: "+ seeds.get(pos) +" "+seeds.get(pos+1));
			if(pos<seeds.size()-1)
			{
				//mark as begin
				Path newCandidate = new Path();
				newCandidate.setBegin_pos(seeds.get(pos+1));
				newCandidate.setFullpaths(candiate.getRepeatsEndedpaths_r());
				newCandidate.setToBeAlign(readSequence.substring(newCandidate.getBegin_pos()-100, newCandidate.getBegin_pos()+ks.getKmerSize()));//overflow
				newCandidate.setRepeatsEndedpaths(new ArrayList<StringBuilder>());
				MyUtil.logging(seeds.toString());
				//System.out.println(seeds.toString());
				newCandidate.setBegin(true);
				for(int i=0; i<=pos;++i)
				{
					seeds.remove(0);
					MyUtil.logging(seeds.toString());
					//System.out.println(seeds.toString());
				}
				candidatesList.clear();
				MyUtil.logging("linker found use right seed as beginning");
				MyUtil.logging(newCandidate.toString());
				//System.out.println("linker found use right seed as beginning");
				//System.out.println(newCandidate.toString());
				candidatesList.add(newCandidate);
				//now I have to update i to pos-> if not inconstancy is appearing
				if(pos+2>=seeds.size())
				{
					lastSeeds(candidatesList, new ArrayList<Boolean>());
				}
//				for(int i=0; i<=pos;++i)
//				{
//					MyUtil.logging("done internally counter "+i+" pos "+pos);
//					//System.out.println("done internally counter "+i+" pos "+pos);
//					if(i+1>=seeds.size())
//					{
//						lastSeeds(candidatesList, new ArrayList<Boolean>());
//						break;
//					}
//					inbetweenSeed(candidatesList, i,new ArrayList<Boolean>());
//				}				
			}
			else if(pos>=seeds.size()-1)
			{
				//mark as end
				Path newCandidate = new Path();
				newCandidate.setEnd_pos(seeds.get(pos));
				if(candiate.getRepeatsEndedpaths().size()>0 && candiate.getRepeatsEndedpaths().get(0).toString()!="")
				{
					newCandidate.setFullpaths(candiate.getRepeatsEndedpaths());
				}
				else
				{
					newCandidate.setFullpaths(candiate.getRepeatsEndedpaths_r());
				}
					
					
				MyUtil.logging("linker found use left seed as ending");
				//System.out.println("linker found use left seed as ending");
				newCandidate.setToBeAlign(readSequence.substring(newCandidate.getEnd_pos(), newCandidate.getEnd_pos()+100));//overflow
				newCandidate.setRepeatsEndedpaths(new ArrayList<StringBuilder>());
				newCandidate.setEnd(true);
				for(int i=pos; i<=seeds.size();++i)
				{
					seeds.remove(seeds.size()-1);
				}
				//System.out.println("linker found use left seed as ending");
				MyUtil.logging(newCandidate.toString());
				//System.out.println(newCandidate.toString());
				candidatesList.add(newCandidate);
			}
			else 
			{
				int lengthLeftToRight = candiate.getRepeatsEndedpaths().get(0).length();
				int lengthRightToLeft = candiate.getRepeatsEndedpaths_r().get(0).length();
				if(distance < lengthLeftToRight || distance< lengthRightToLeft)
				{
					//maybe we have here sequences, which are not located on the same chr!
					if(!this.contamination)
					{
						this.contamination = true;
						this.contaminationBreakPoints = new ArrayList<>();
					}
					this.contaminationBreakPoints.add(pos);
				}
				//distance
			}
			++counter;
			return true;
		}
		return false;
	}
	

	public void glueFragments(List<Path>results, List<String>endResult, List<String> marked, List<String>corrected)
	{
		StringBuilder newPacBioRead= new StringBuilder();
		StringBuilder newPacBioReadCorrectedCode= new StringBuilder();
		StringBuilder newPacBioReadMarked = new StringBuilder();
		for(int i=0; i< endResult.size();++i)
		{
			//System.out.println(i);
			if(i==0)
			{
				newPacBioRead.append(endResult.get(i));
				newPacBioReadCorrectedCode.append(corrected.get(i));
				newPacBioReadMarked.append(marked.get(i));
			}
			else
			{ 	
				//cut the last seed out! overhang
				if(endResult.get(i).length()>ks.getKmerSize())
				{
					newPacBioRead.append(endResult.get(i).substring(ks.getKmerSize()));
				}
				//System.out.println(corrected.get(i));
				//System.out.println("Size "+corrected.get(i).length());
				newPacBioReadCorrectedCode.append(corrected.get(i).substring(ks.getKmerSize())); //TODO check this
				newPacBioReadMarked.append(marked.get(i).substring(ks.getKmerSize()));
			}
		}
		endResult.clear();
		marked.clear();
		corrected.clear();
		endResult.add(newPacBioRead.toString());
		corrected.add(newPacBioReadCorrectedCode.toString());
		marked.add(newPacBioReadMarked.toString());
	}
	
	

	private int getTheBestAlignment2(List<Future<Double>> list, List<StringBuilder> candidate, Pair<StringBuilder,Double> result, int i, int j) throws InterruptedException, ExecutionException
	{
		
		double score = 0;
		int counter = 0;
		//System.out.println("candidate List:"+ candidate.toString());
		//System.out.println(i +" "+j);
		
		List<StringBuilder>bestCandidates = new ArrayList<StringBuilder>();
		for(int z=0; z <candidate.size();++z)
		{
			if(z+i>=j)
			{
				break;
			}
			double alignment_result = list.get(z+i).get();
			
			if(bestCandidates.size()==0)
			{ 						
				bestCandidates.add(candidate.get(0));
				score=alignment_result;
				counter=1;
			}
			else
			{
				if(score<alignment_result)
				{
					bestCandidates.clear();
					bestCandidates.add(candidate.get(counter));
					score=alignment_result;
					counter=z;
				}
				else if(score==alignment_result)
				{
					bestCandidates.add(candidate.get(counter));
				}
			}
		}		
		if(bestCandidates.size()>1)
		{
			result.setFirst(bestCandidates.get(generator.nextInt(bestCandidates.size())));	
		}
		else
		{
			if(bestCandidates.size()==0)
			{
				//System.out.println("empty String");
				result.setFirst(new StringBuilder(""));
			}
			else
			{
				//System.out.println("first entry String");
				result.setFirst(bestCandidates.get(0));
			}
		}
		result.setSecond(score);
		return counter;
	}
	

	
	public void prepareFragments2(List<Path> results,List<String>endResult, List<String> marked, List<String>corrected) throws InterruptedException, ExecutionException
	{
		List<Integer> alignmentToBeDone = new ArrayList<Integer>();
		//ExecutorService executor = Executors.newFixedThreadPool(2);
		//List<Future<AlignmentObject>> list = new ArrayList<Future<AlignmentObject>>();
		List<AlignmentObject> list =new ArrayList<AlignmentObject>();
		MyUtil.logging("prepare fragments \n");
		//System.out.println("prepare fragments \n");
		for(int i=0; i < results.size();++i)
		{
			MyUtil.logging(String.valueOf(i));
			MyUtil.logging(results.get(i).toString());
			//MyUtil.logging(results.get(i).getResult().toString());
			//System.out.println(i);
			//System.out.println(results.get(i).toString());
			//System.out.println(results.get(i).getResult());
			////System.out.println("test "+ (i ==0 && results.get(i).getResult().toString()!=""));
			if(results.get(i).getType() || (i ==0 && results.get(i).getResult().toString()!="") || (i==results.size()-1 && results.get(i).getResult().toString()!=""))
			{					
				AlignmentObject tempWorker = new AlignmentObject();
				tempWorker.setTemplate(results.get(i).getToBeAlign());
				if(results.get(i).getType())
				{
					MyUtil.logging("Type true");
					//System.out.println("Type true");
					//frage was passiert wenn alles leer ist
					if(results.get(i).getRight()==null && results.get(i).getLeft()==null)
					{
						alignmentToBeDone.add(0);
					}
					else
					{
						MyUtil.logging("left right alignment");
						MyUtil.logging("left fragment "+ results.get(i).getLeft());
						//System.out.println("left right alignment");
						//System.out.println("left fragment "+ results.get(i).getLeft());
						tempWorker.setA(results.get(i).getLeft().toString());
						//int pro=results.get(i).getLeft().length()*10/100;
						if(results.get(i).getLeft().length() >= results.get(i).getToBeAlign().length())
						{
							tempWorker.setTemplate(results.get(i).getToBeAlign().substring(0,results.get(i).getToBeAlign().length()));
						}
						else							
						tempWorker.setTemplate(results.get(i).getToBeAlign().substring(0,results.get(i).getLeft().length()));
						tempWorker.setGap(2);
						tempWorker.setEx(1);
						tempWorker.setFlag(true);
						ThreadAlignmentTraceback worker = new ThreadAlignmentTraceback(tempWorker);
						//Callable<AlignmentObject> worker = new ThreadAlignmentTraceback(tempWorker);
						//Future<AlignmentObject> submit = executor.submit(worker);
						//list.add(submit);
						AlignmentObject temp = worker.runIt();
						MyUtil.logging("left");
						MyUtil.logging(temp.toString());
						//System.out.println("left");
						//System.out.println(temp.toString());
						list.add(temp);
						tempWorker.setA(results.get(i).getRight().toString());
						if(results.get(i).getToBeAlign().length()<results.get(i).getRight().length())
						{
							tempWorker.setTemplate(results.get(i).getToBeAlign());
						}
						else
						{
							tempWorker.setTemplate(results.get(i).getToBeAlign().substring(results.get(i).getToBeAlign().length()-(results.get(i).getRight().length()),results.get(i).getToBeAlign().length()));
						}
						ThreadAlignmentTraceback worker2 = new ThreadAlignmentTraceback(tempWorker);
//						Callable<AlignmentObject> worker2 = new ThreadAlignmentTraceback(tempWorker);
//						Future<AlignmentObject> submit2 = executor.submit(worker2);
//						list.add(submit2);
						temp = worker2.runIt();
						MyUtil.logging("right");
						MyUtil.logging(temp.toString());
						//System.out.println("right");
						//System.out.println(temp.toString());
						list.add(temp);
						alignmentToBeDone.add(3);	
					}
				}
				else 
				{	
					MyUtil.logging("Resulting String "+results.get(i).getResult().toString()+" "+results.get(i).getResult().toString().length());
					//System.out.println("Resulting String "+results.get(i).getResult().toString()+" "+results.get(i).getResult().toString().length());
					if(results.get(i).getResult() != null && results.get(i).getResult().toString().length() ==0)
					{
						MyUtil.logging("empty results");
						MyUtil.logging(results.get(i).toString());
						MyUtil.logging("no fragments empty string");
						//System.out.println("empty results");
						//System.out.println(results.get(i).toString());
						//System.out.println("no fragments empty string");
						alignmentToBeDone.add(0);
					}
					else
					{
						MyUtil.logging("fragment alignment");
						//System.out.println("fragment alignment");
						tempWorker.setA(results.get(i).getResult().toString());
						tempWorker.setTemplate(results.get(i).getToBeAlign());
//						if(results.get(i).getToBeAlign().length()>results.get(i).getResult().length())
//						{	
//							if(i==0)
//							{
//		tempWorker.setTemplate(results.get(i).getToBeAlign().substring(results.get(i).getToBeAlign().length()-results.get(i).getResult().length()-2,results.get(i).getToBeAlign().length())); //das ist falsch, warum lande ich hier �berhaupt?
//							}
//							else
//							{
//								tempWorker.setTemplate(results.get(i).getToBeAlign().substring(0,results.get(i).getResult().length())); 
//							}								
//						}
//						else
//						{
//							
//						}
							
						tempWorker.setGap(2);
						tempWorker.setEx(1);
						ThreadAlignmentTraceback worker = new ThreadAlignmentTraceback(tempWorker);
//						Callable<AlignmentObject> worker = new ThreadAlignmentTraceback(tempWorker);
//						Future<AlignmentObject> submit = executor.submit(worker);
//						list.add(submit);
						AlignmentObject temp = worker.runIt();
						MyUtil.logging(temp.toString());
						//System.out.println(temp.toString());
						list.add(temp);
						if(i==0)
						{
							alignmentToBeDone.add(1);
						}
						else if(i==results.size()-1)
						{
							alignmentToBeDone.add(2);
						}
					}
				}
			}
			else
			{
				alignmentToBeDone.add(0);
			}
		}
		//executor.shutdown();
		//now we have to collect the alignments, trim begin and end if corretion is to long, if not fill them with Ns 
//		List<String> endResult = new ArrayList<String>();
//		List<String> marked = new ArrayList<String>();
//		List<String> corrected = new ArrayList<String>();
		MyUtil.logging(" alignment to be done :"+alignmentToBeDone.toString());
		//System.out.println(" alignment to be done :"+alignmentToBeDone.toString());
		int counter=0;
		for(int i=0; i < alignmentToBeDone.size();++i)
		{
			//System.out.println("step "+i);
			if(alignmentToBeDone.get(i)==0)
			{
				caseAllorNothing(results.get(i), endResult,corrected,marked);
			}
			else if(alignmentToBeDone.get(i)==1)
			{
				if(results.get(i).getToBeAlign().length()>results.get(i).getResult().length()+2)
				{
					AlignmentObject tempObject = list.get(counter);
					StringBuilder a = new StringBuilder(tempObject.getA());
					StringBuilder template = new StringBuilder(tempObject.getTemplate());
					a.reverse();
					template.reverse();
					int startpoint = results.get(i).getToBeAlign().length()-results.get(i).getResult().length()-2;
					for(int j=startpoint; j>=0;--j)
					{
						a.append('-');
						template.append(results.get(i).getToBeAlign().charAt(j));
					}
					a.reverse();
					template.reverse();
					tempObject.setA(a.toString());
					tempObject.setTemplate(template.toString());
					caseBeginingTrimming(results.get(i),tempObject, endResult,corrected,marked);
				}
				else
				{
					caseBeginingTrimming(results.get(i),list.get(counter), endResult,corrected,marked);
				}
				++counter;
			}
			else if(alignmentToBeDone.get(i)==2)
			{
				if(results.get(i).getToBeAlign().length()>results.get(i).getResult().length()+2)
				{
					AlignmentObject tempObject = list.get(counter);
					StringBuilder a = new StringBuilder(tempObject.getA());
					StringBuilder template = new StringBuilder(tempObject.getTemplate());
					for(int j=tempObject.getA().length(); j< results.get(i).getToBeAlign().length();++j)
					{
						a.append('-');
						template.append(results.get(i).getToBeAlign().charAt(j));
					}
					tempObject.setA(a.toString());
					tempObject.setTemplate(template.toString());
					caseEndTrimming(results.get(i),tempObject, endResult,corrected,marked);
				}
				else
				{
					caseEndTrimming(results.get(i),list.get(counter), endResult,corrected,marked);
				}
				++counter;
			}
			else if(alignmentToBeDone.get(i)==3)
			{
				case2Sides(results.get(i),list.get(counter),list.get(counter+1),endResult,corrected,marked);
				++counter;
				++counter;
			}
			//System.out.println("endRes "+endResult.size());
			//System.out.println("corrected "+corrected.size());
			//System.out.println("marked "+marked.size());
		}
	}
		
	public void prepareFragments(List<Path> results,List<String>endResult, List<String> marked, List<String>corrected) throws InterruptedException, ExecutionException
	{
		List<Integer> alignmentToBeDone = new ArrayList<Integer>();
		ExecutorService executor = Executors.newFixedThreadPool(2);
		List<Future<AlignmentObject>> list = new ArrayList<Future<AlignmentObject>>();
		
		////System.out.println("prepare fragments \n");
		for(int i=0; i < results.size();++i)
		{
			////System.out.println(i);
			////System.out.println(results.get(i).toString());
			
			if(results.get(i).getType() || (i ==0 && !results.get(i).getResult().equals("")) || (i==results.size()-1 && !results.get(i).getResult().equals("")))
			{					
				AlignmentObject tempWorker = new AlignmentObject();
				tempWorker.setTemplate(results.get(i).getToBeAlign());
				if(results.get(i).getType())
				{
					//frage was passiert wenn alles leer ist
					if(results.get(i).getRight().length()==0 && results.get(i).getLeft().length()==0)
					{
						alignmentToBeDone.add(0);
					}
					else
					{
						tempWorker.setA(results.get(i).getLeft().toString());
						tempWorker.setGap(2);
						tempWorker.setEx(1);
						Callable<AlignmentObject> worker = new ThreadAlignmentTraceback(tempWorker);
						Future<AlignmentObject> submit = executor.submit(worker);
						list.add(submit);
						tempWorker.setA(results.get(i).getRight().toString());
						worker = new ThreadAlignmentTraceback(tempWorker);
						submit = executor.submit(worker);
						list.add(submit);
						alignmentToBeDone.add(3);
					}
				}
				else 
				{
					if(results.get(i).getResult().equals(""))
					{
						alignmentToBeDone.add(0);
					}
					else
					{
						tempWorker.setA(results.get(i).getResult().toString());
						tempWorker.setGap(2);
						tempWorker.setEx(1);
						Callable<AlignmentObject> worker = new ThreadAlignmentTraceback(tempWorker);
						Future<AlignmentObject> submit = executor.submit(worker);
						list.add(submit);
						if(i==0)
						{
							alignmentToBeDone.add(1);
						}
						else if(i==results.size()-1)
						{
							alignmentToBeDone.add(2);
						}
					}
				}
			}
			else
			{
				alignmentToBeDone.add(0);
			}
		}
		executor.shutdown();
		//now we have to collect the alignments, trim begin and end if corretion is to long, if not fill them with Ns 
//		List<String> endResult = new ArrayList<String>();
//		List<String> marked = new ArrayList<String>();
//		List<String> corrected = new ArrayList<String>();
		////System.out.println(" alignment to be done :"+alignmentToBeDone.toString());
		int counter=0;
		for(int i=0; i < alignmentToBeDone.size();++i)
		{
			if(alignmentToBeDone.get(i)==0)
			{
				caseAllorNothing(results.get(i), endResult,corrected,marked);
			}
			else if(alignmentToBeDone.get(i)==1)
			{
				caseBeginingTrimming(results.get(i),list.get(counter).get(), endResult,corrected,marked);
				++counter;
			}
			else if(alignmentToBeDone.get(i)==2)
			{
				caseEndTrimming(results.get(i),list.get(counter).get(), endResult,corrected,marked);
				++counter;
			}
			else if(alignmentToBeDone.get(i)==3)
			{
				case2Sides(results.get(i),list.get(counter).get(),list.get(counter+1).get(),endResult,corrected,marked);
				++counter;
				++counter;
			}
		}
	}
	
	private void helpfunction(AlignmentObject align, Path result, boolean dir, List<String>resultingString, List<String>corrected, List<String> marked)
	{
		StringBuilder alignmentPacCorr = new StringBuilder(align.getA());
		StringBuilder alignmentPac= new StringBuilder(align.getTemplate());
		
		//System.out.println("a "+ alignmentPacCorr);
		//System.out.println("template "+ alignmentPac);
		if(dir)
		{
			alignmentPac.reverse();
			alignmentPacCorr.reverse();
		}
		int bestVal=0;
		int pos=0;
		int counter=0;
		for(int i=0; i <alignmentPacCorr.length();++i)
		{
			if(alignmentPacCorr.charAt(i)=='-')
			{
				++counter;
			}
			else
			{
				if(bestVal<counter)
				{
					bestVal=counter;
					pos=i-counter;
				}
				counter=0;
			}
		}
		if(bestVal<counter)
		{
			bestVal=counter;
			pos=alignmentPacCorr.length()-1-counter;
			counter=0;
		}
		
		StringBuilder a=new StringBuilder();
		StringBuilder b=new StringBuilder();
		StringBuilder c=new StringBuilder();
		
		if(dir)
		{
			b.append(result.getResult().reverse());
		}
		else
		{
			b.append(result.getResult());
		}
		for(int i=0; i < alignmentPacCorr.length();++i)
		{
			if(i>pos)
			{
				if(alignmentPacCorr.charAt(i)!='-')
				{
					c.append(alignmentPacCorr.charAt(i));
					a.append("C");
				}
				else 
				{
					//System.out.print(c.length() +" "+ result.getResult().length());
					if(c.length()>=result.getResult().length() && alignmentPac.charAt(i)!='-')
					{
						b.append("N");
						a.append("N");
						c.append(alignmentPac.charAt(i));
					}
				}
			}
			else
			{
				if(alignmentPacCorr.charAt(i)!='-')
				{
					c.append(alignmentPacCorr.charAt(i));
					if(i<ks.getKmerSize())
					a.append("S");
					else
					a.append("C");
				}
			}
		}
		if(dir)
		{
			a.reverse();
			b.reverse();
			c.reverse();
		}
		//System.out.println("3 7");
		//System.out.println("a "+c);
		//System.out.println("m "+a);
		//System.out.println("r "+b);
		resultingString.add(c.toString());
		marked.add(a.toString());
		corrected.add(b.toString());

	}
	
	
	private void trim(AlignmentObject align, Path result, boolean dir, List<String>resultingString, List<String>corrected, List<String> marked)
	{
		//System.out.println("dir "+dir);
		if(dir) //beginning trimming
		{
			if(seeds.get(0)==0)
			{
				StringBuilder a = new StringBuilder();
				for(int i=0; i< result.getResult().length();++i)
				{
					if(i<ks.getKmerSize())
					{
						a.append("S");
					}
					else
					{
						a.append("C");
					}
				}
//				System.out.println("1");
//				System.out.println("a "+result.getResult());
//				System.out.println("m "+marked);
//				System.out.println("c "+result.getResult());
				marked.add(a.toString());
				resultingString.add(result.getResult().toString());
				corrected.add(result.getResult().toString());
			}
			else
			{	
				if(result.getResult().length()>result.getToBeAlign().length())
				{
					int pos=0;
					for(int i=0; i < align.getTemplate().length();++i)
					{
						if(align.getTemplate().charAt(i)!='-')
						{
							pos=i;
							break;
						}
					}
					StringBuilder a=new StringBuilder();
					//StringBuilder b=new StringBuilder();
					for(int i=0; i<result.getResult().length();++i)
					{
						if(i>=result.getResult().length()-ks.getKmerSize())
						{
							a.append("S");
						}
						else if(i>pos)
						{
							a.append("C");
						}
						else
						{
							a.append("T");
						}
					}
//					System.out.println("2");
//					System.out.println("a "+result.getResult().substring(pos));
//					System.out.println("m "+a);
//					System.out.println("c "+result.getResult());
					marked.add(a.toString());
					resultingString.add(result.getResult().substring(pos));
					corrected.add(result.getResult().toString());
				}
				else if(result.getResult().length()<result.getToBeAlign().length())
				{
					helpfunction(align,result,true,resultingString,corrected,marked);			
				}
				else
				{
					StringBuilder a = new StringBuilder();
					for(int i=0; i<result.getResult().length();++i)
					{
						if(i>result.getResult().length()-ks.getKmerSize())
						{
							a.append("S");
						}
						else
						{
							a.append("C");
						}
					}
//					System.out.println("4");
//					System.out.println("a "+result.getResult());
//					System.out.println("m "+a);
//					System.out.println("c "+result.getResult());
					marked.add(a.toString());
					corrected.add(result.getResult().toString());
					resultingString.add(result.getResult().toString());
				}
			}
		}
		else //the other case 
		{
			if(seeds.get(seeds.size()-1)==result.getResult().length()-ks.getKmerSize())
			{
				StringBuilder a = new StringBuilder();
				for(int i=0; i < result.getResult().length();++i)
				{
					if(i>=result.getResult().length()-ks.getKmerSize())
					{
						a.append("S");
					}
					else
					{
						a.append("C");
					}
				}
//				System.out.println("5");
//				System.out.println("a "+result.getResult());
//				System.out.println("m "+a);
//				System.out.println("c "+result.getResult());
				
				marked.add(a.toString());
				corrected.add(result.getResult().toString());
				resultingString.add(result.getResult().toString());
			}
			else
			{
//				System.out.println(result.getResult());
//				System.out.println(result.getToBeAlign());
//				System.out.println();
//				System.out.println(align.getTemplate());
//				System.out.println(align.getA());
								
				if(result.getResult().length()>result.getToBeAlign().length())
				{
					int pos=0;
					int gap_pos=0;
					int bestVal_gap=0;
					int gap_counter=0;
					int counter=0;
					int bestVal=0;
					//maybe change to longest gap or mismatch#
					
					for(int i=0; i<align.getTemplate().length();++i)
					{
						if(align.getTemplate().charAt(i)==align.getA().charAt(i))
						{
							if(align.getTemplate().charAt(i)!='-')
							{
								if(bestVal_gap<gap_counter)
								{
									gap_pos=i-bestVal_gap;
									bestVal_gap=gap_counter;
								}
								gap_counter=0;
							}
							else if(align.getTemplate().charAt(i)=='-')
							{
								++gap_counter;
							}
							
							if(bestVal<counter)
							{
								bestVal=counter;
								pos=i-bestVal;
							}
							counter=0;
						}
						else
						{
							++counter;
						}
					}
					if(bestVal_gap<gap_counter)
					{
						gap_pos=align.getTemplate().length()-1-bestVal_gap;
						gap_counter=0;
					}
					if(bestVal<counter)
					{
						bestVal=counter;
						pos=align.getTemplate().length()-1-bestVal;
						counter=0;
					}
					
					if(gap_pos<pos && pos > result.getResult().length())
					{
						pos = gap_pos;
					}
//					for(int i=0;i<align.getTemplate().length();++i)
//					{
//						if(align.getTemplate().charAt(i)=='-')
//						{
//							if(bestVal<counter)
//							{
//								bestVal=counter;
//								pos=i;
//							}
//							counter=0;
//						}
//						else
//						{
//							++counter;
//						}
//					}
//					if(bestVal<counter)
//					{
//						bestVal=counter;
//						pos=align.getTemplate().length()-1;
//						counter=0;
//					}
					
					
					StringBuilder a=new StringBuilder();
					for(int i=0; i<result.getResult().length();++i)
					{
						if(i<ks.getKmerSize()-1)
						{
							a.append("S");
						}
						else if(i<pos)
						{
							a.append("C");
						}
						else
						{
							a.append("T");
						}
					}
//					System.out.println("6");
//					System.out.println("pos: "+pos);
//					System.out.println("result: "+ result.getResult().length());
//					System.out.println("a "+result.getResult().substring(0,pos));
//					System.out.println("m "+a);
//					System.out.println("c "+result.getResult());
					marked.add(a.toString());
					resultingString.add(result.getResult().substring(0,pos));
					corrected.add(result.getResult().toString());
				}
				else if(result.getResult().length()<result.getToBeAlign().length())
				{	
					helpfunction(align,result,false,resultingString,corrected,marked);
				}
				else
				{
					StringBuilder a = new StringBuilder();
					for(int i=0; i<result.getResult().length();++i)
					{
						if(i>result.getResult().length()-ks.getKmerSize())
						{
							a.append("S");
						}
						else
						{
							a.append("C");
						}
					}
//					System.out.println("a "+result.getResult());
//					System.out.println("m "+a);
//					System.out.println("c "+result.getResult());

					marked.add(a.toString());
					corrected.add(result.getResult().toString());
					resultingString.add(result.getResult().toString());
				}
			}
		}
	}
	
	private int findGapPos(String template, char b,boolean dir)
	{
		int counter=0;
		int bestVal=0;
		int pos=0;
		StringBuilder a = new StringBuilder(template);
		if(!dir)
		{
			a.reverse();
		}
		for(int i=0; i < a.length();++i)
		{
			if(a.charAt(i)==b)
			{
				++counter;
			}
			else 
			{
				if(counter>bestVal)
				{
					bestVal=counter;
					pos=i-counter;
				}
				counter=0;
			}
		}
		if(counter >0)
		{
			if(counter>bestVal)
			{
				bestVal=counter;
				pos=a.length()-1-counter;
			}
		}
		//System.out.println(a);
		//System.out.println("pos "+ pos);
		return pos;
	}
	
	private void trim(AlignmentObject alignLeft, AlignmentObject alignRight,Path result, List<String>resultingString, List<String>corrected, List<String> marked)
	{
		if(result.getRight().length()>=result.getToBeAlign().length() && result.getLeft().length()>=result.getToBeAlign().length() )
		{
			//System.out.println("right seed bridge the distance between two seeds  nearly \n");
			AlignmentObject tempWorker = new AlignmentObject();
			StringBuilder sb = new StringBuilder(result.getLeft());
			StringBuilder sb2 =new StringBuilder(result.getRight());
//			if(result.getLeft().length()>result.getRight().length())
//			{
//				sb2 = new StringBuilder(result.getRight().substring(0,result.getRight().length()));
//			}
//			else
//			{
//				sb2 = new StringBuilder(result.getRight().substring(0,result.getLeft().length()));
//			}
			
			tempWorker.setA(sb.toString());
			tempWorker.setTemplate(sb2.toString());
			tempWorker.setGap(2);
			tempWorker.setEx(1);
			AlignmentObject p= new NeedlemanWunsch(tempWorker).affineCompareWithTraceBack();
			//now scan the alignment
			//System.out.println("a "+ p.getA());
			//System.out.println("tem "+ p.getTemplate());
			
			int counter=0;
			int temp_counter=0;
			for(int i=0; i < p.getA().length();++i)
			{
				if(counter>=result.getLeft().length())
				{
					break;
				}
				//now reconstruct seed1 with the aligment
				if(p.getA().charAt(i)!='-')
				{
					++counter;
				}
				if(p.getTemplate().charAt(i)!='-')
				{
					++temp_counter;
				}
			}
			
			StringBuilder a = new StringBuilder();
			StringBuilder resultString = new StringBuilder();
			StringBuilder correct = new StringBuilder();
			for(int i=0; i<result.getLeft().length();++i)
			{
				if(i<ks.getKmerSize())
				{
					a.append("S");	
				}
				else
				{
					a.append("C");
				}
			}
			resultString.append(result.getLeft());
			correct.append(result.getLeft());
			for(int j=temp_counter;j<result.getRight().length();++j)
			{
				if(j>=result.getRight().length()-ks.getKmerSize())
				{
					a.append("S");
				}
				else
				{
					a.append("C");
				}
			}
			resultString.append(result.getRight().substring(temp_counter));
			correct.append(result.getRight().substring(temp_counter));
			resultingString.add(resultString.toString());
			marked.add(a.toString());
			corrected.add(correct.toString());
		}
		else
		{
			//left seed
			//find the longest distance of '-'
			//System.out.println("left side "+ alignLeft.toString());
			//System.out.println("right side "+ alignRight.toString());
			//System.out.println("ref : "+result.getToBeAlign());
			int leftBorder = findGapPos(alignLeft.getA(), '-', true);
			int rightBorder =findGapPos(alignRight.getA(), '-', false);
			
			if(rightBorder==0)
			{
				rightBorder=ks.getKmerSize();
			}
			rightBorder = result.getToBeAlign().length()-rightBorder;
			
			
			StringBuilder a = new StringBuilder();
			StringBuilder resultString = new StringBuilder();
			StringBuilder correct = new StringBuilder();
			for(int i=0; i<result.getLeft().length();++i)
			{
				if(i<ks.getKmerSize())
				{
					a.append("S");	
				}
				else
				{
					a.append("C");
				}
			}
			resultString.append(result.getLeft());
			correct.append(result.getLeft());
			
			StringBuilder inbetween = new StringBuilder();
			StringBuilder inbetween2 = new StringBuilder();
			//System.out.println("left and right "+leftBorder + " "+ rightBorder);
			for(int i=leftBorder; i<=rightBorder;++i)
			{
				inbetween.append(result.getToBeAlign().charAt(i));
				inbetween2.append("N");
				a.append("N");
			}
			resultString.append(inbetween);
			correct.append(inbetween2);
			
			StringBuilder temp = new StringBuilder();
			for(int i=0; i<result.getRight().length();++i)
			{
				if(i<ks.getKmerSize())
				{
					temp.append("S");	
				}
				else
				{
					temp.append("C");
				}
			}
			temp.reverse();
			a.append(temp);
			resultString.append(result.getRight());
			correct.append(result.getRight());
			
			resultingString.add(resultString.toString());
			corrected.add(correct.toString());
			marked.add(a.toString());		
		}
	}
	
	private void case2Sides(Path result,AlignmentObject alignLeft, AlignmentObject alignRight,List<String>resultingString, List<String>corrected, List<String> marked)
	{
		trim(alignLeft,alignRight,result,resultingString,corrected,marked);
	}
	
	private void caseEndTrimming(Path result,AlignmentObject alignment,List<String>resultString,List<String>correction, List<String>marked)
	{
		trim(alignment, result, false, resultString, correction, marked);
	}
	
	private void caseBeginingTrimming(Path result,AlignmentObject alignment,List<String>resultString,List<String>correction, List<String>marked)
	{
		trim(alignment, result, true, resultString, correction, marked);
	}
	
	private void caseAllorNothing(Path result, List<String>resultString, List<String>correction, List<String>marked)
	{
		if(result.getResult()==null ||result.getResult().length()==0 || result.getResult().toString()=="")
		{
		//	System.out.println("use pac bio string");
			resultString.add(result.getToBeAlign());
			StringBuilder a = new StringBuilder();
			for(int i=0; i < result.getToBeAlign().length();++i)
			{
				if(i<ks.getKmerSize())
				{
					a.append("S");
				}
				else if(i>=result.getToBeAlign().length()-ks.getKmerSize())
				{
					a.append("S");
				}
				else
				a.append("N");
			}
			marked.add(a.toString());
			correction.add(result.getToBeAlign());			
		}
		else
		{
			//System.out.println("use fragment");
			resultString.add(result.getResult().toString());
			StringBuilder a = new StringBuilder();
			for(int i=0; i < result.getResult().length();++i)
			{
				if(i<ks.getKmerSize())
				{
					a.append("S");
				}
				else if(i>=result.getResult().length()-ks.getKmerSize())
				{
					a.append("S");
				}
				else
				{
					a.append("C");	
				}
				
			}
			marked.add(a.toString());
			correction.add(result.getResult().toString());
		}
		//System.out.println(resultString.toString());
		//System.out.println(marked.toString());
		//System.out.println(correction.toString());
	}
	

	
	
	public void callAlignment2(List<Path>candidateList,List<Path>result) throws InterruptedException, ExecutionException
	{
		for(int i =0; i < candidateList.size();++i)
		{			
			//normal or do we have to handle with repeats inbetween?
			if(candidateList.get(i).getType()) // we do not found one unique bridge between two seeds!
			{
				ExecutorService executor = Executors.newFixedThreadPool(40);
				List<Future<Double>> list = new ArrayList<Future<Double>>();
				MyUtil.logging(String.valueOf(i));
				MyUtil.logging("Candidate Size Full:"+ candidateList.get(i).getFullpaths());
				MyUtil.logging("Candidate Size Sparse:"+ candidateList.get(i).getRepeatsEndedpaths());
				MyUtil.logging("Candidate Size Sparse_R:"+ candidateList.get(i).getRepeatsEndedpaths_r());
				if(candidateList.get(i).getStoppedTemplate()!=null)
				{
					MyUtil.logging("StoppTemplate :" + candidateList.get(i).getStoppedTemplate().toString());
					MyUtil.logging("StoppTemplate_R :" + candidateList.get(i).getStoppedTemplate_R().toString());
				}
				
//				System.out.println(i);
//				System.out.println("Candidate Size Full:"+ candidateList.get(i).getFullpaths());
//				System.out.println("Candidate Size Sparse:"+ candidateList.get(i).getRepeatsEndedpaths());
//				System.out.println("Candidate Size Sparse_R:"+ candidateList.get(i).getRepeatsEndedpaths_r());
//				System.out.println("StoppTemplate :" + candidateList.get(i).getStoppedTemplate().toString());
//				System.out.println("StoppTemplate_R :" + candidateList.get(i).getStoppedTemplate_R().toString());
				
				
//				ExecutorService executor = Executors.newFixedThreadPool(40);
//				List<Future<Double>> list = new ArrayList<Future<Double>>();
				//List<Double> values = new ArrayList<Double>();
				for(int j=0;j< candidateList.get(i).getFullpaths().size();++j)
				{
					Callable<Double> worker = new ThreadAlignment(candidateList.get(i).getFullpaths().get(j).toString(),candidateList.get(i).getToBeAlign(), 2, 1);
					//values.add(worker.doAlignment());
					Future<Double> submit = executor.submit(worker);
					list.add(submit);
				}
				for(int j=0;j< candidateList.get(i).getRepeatsEndedpaths().size();++j)
				{
					Callable<Double> worker = new ThreadAlignment(candidateList.get(i).getRepeatsEndedpaths().get(j).toString(),candidateList.get(i).getStoppedTemplate().get(j), 2, 1);
					//values.add(worker.doAlignment());
					Future<Double> submit = executor.submit(worker);
					list.add(submit);
				}
				for(int j=0;j< candidateList.get(i).getRepeatsEndedpaths_r().size();++j)
				{
					Callable<Double> worker = new ThreadAlignment(candidateList.get(i).getRepeatsEndedpaths_r().get(j).toString(),candidateList.get(i).getStoppedTemplate_R().get(j), 2, 1);
					//values.add(worker.doAlignment());
					Future<Double> submit = executor.submit(worker);
					list.add(submit);
				}	
				executor.shutdown();
				////System.out.println(values.toString());
				Pair<StringBuilder, Double> fullpath = new Pair<StringBuilder, Double>();
				if(candidateList.get(i).getFullpaths().size()==1 && candidateList.get(i).getFullpaths().get(0).indexOf("")!=-1)
				{
					fullpath.setFirst(new StringBuilder(""));
					fullpath.setSecond(Double.NEGATIVE_INFINITY);
				}
				else
				{
					getTheBestAlignment2(list, candidateList.get(i).getFullpaths(), fullpath, 0, candidateList.get(i).getFullpaths().size());
				}
				int begin =candidateList.get(i).getFullpaths().size();
				Pair<StringBuilder, Double> brokenPath = new Pair<StringBuilder, Double>();
				getTheBestAlignment2(list, candidateList.get(i).getRepeatsEndedpaths(), brokenPath,begin,candidateList.get(i).getFullpaths().size()+candidateList.get(i).getRepeatsEndedpaths().size());
				
				Pair<StringBuilder, Double> brokenPath_r = new Pair<StringBuilder, Double>();
				begin = candidateList.get(i).getFullpaths().size()+candidateList.get(i).getRepeatsEndedpaths().size();
				getTheBestAlignment2(list, candidateList.get(i).getRepeatsEndedpaths_r(), brokenPath_r,begin,list.size());
				
				Path temp = new Path();
				if(fullpath.getSecond()>(brokenPath.getSecond()+brokenPath_r.getSecond()))
				{
					temp.setResult(fullpath.getFirst());
				}
				else
				{
					temp.setType(true);
					temp.setLeft(brokenPath.getFirst());
					temp.setRight(brokenPath_r.getFirst());//they are not overlapping -> if overlapping either linker or not
				}
				temp.setToBeAlign(candidateList.get(i).getToBeAlign());
				fullpath=null;
				brokenPath=null;
				MyUtil.logging(temp.toString());
				//System.out.println(temp.toString());
				result.add(temp);				
			}
			else
			{
				MyUtil.logging(String.valueOf(i));
				MyUtil.logging("Candidate Size Full:"+ candidateList.get(i).getFullpaths());
				MyUtil.logging("Candidate Size Sparse:"+ candidateList.get(i).getRepeatsEndedpaths());
				//System.out.println(i);
				//System.out.println("Candidate Size Full:"+ candidateList.get(i).getFullpaths());
				//System.out.println("Candidate Size Sparse:"+ candidateList.get(i).getRepeatsEndedpaths());		
				if(candidateList.get(i).getFullpaths().size()==1 && candidateList.get(i).getFullpaths().get(0).indexOf("")!=-1 && candidateList.get(i).getRepeatsEndedpaths().size()==0)
				{
					MyUtil.logging("one solution");
					//System.out.println("one solution");
					candidateList.get(i).setResult(candidateList.get(i).getFullpaths().get(0));
					result.add(candidateList.get(i));
				}
				else
				{
					ExecutorService executor = Executors.newFixedThreadPool(40);
					List<Future<Double>> list = new ArrayList<Future<Double>>();
				//	List<Double> values = new ArrayList<Double>();
					for(int j=0;j< candidateList.get(i).getFullpaths().size();++j)
					{
						Callable<Double> worker = new ThreadAlignment(candidateList.get(i).getFullpaths().get(j).toString(),candidateList.get(i).getToBeAlign(), 2, 1);
						Future<Double> submit = executor.submit(worker);
						list.add(submit);
						//values.add(worker.doAlignment());
					}
					for(int j=0;j< candidateList.get(i).getRepeatsEndedpaths().size();++j)
					{
						ThreadAlignment worker = new ThreadAlignment(candidateList.get(i).getRepeatsEndedpaths().get(j).toString(),candidateList.get(i).getStoppedTemplate().get(j), 2, 1);
						Future<Double> submit = executor.submit(worker);
						list.add(submit);
						//values.add(worker.doAlignment());
					}
	//				System.out.println("waiting for the alignment");
					executor.shutdown();
	//				System.out.println("waiting for the alignment done");
					//get the first half
					Pair<StringBuilder, Double> fullpath = new Pair<StringBuilder, Double>();
					//System.out.println(candidateList.get(i).getFullpaths().size()+" "+ candidateList.get(i).getFullpaths().get(0)+" empty \n");
																		
					if(candidateList.get(i).getFullpaths().size()>=1 && candidateList.get(i).getFullpaths().get(0).indexOf("")==-1) 
					{
					//	System.out.println("1_a");
						getTheBestAlignment2(list, candidateList.get(i).getFullpaths(), fullpath, 0, candidateList.get(i).getFullpaths().size());
					}
					else
					{
						//System.out.println("1_b");
						fullpath.setFirst(new StringBuilder(""));
						fullpath.setSecond(Double.NEGATIVE_INFINITY);
					}
					Path temp = new Path();
					
					//System.out.println("1_c");
					if(candidateList.get(i).getRepeatsEndedpaths().size()>0)
					{
						Pair<StringBuilder, Double> brokenPath = new Pair<StringBuilder, Double>();
						getTheBestAlignment2(list, candidateList.get(i).getRepeatsEndedpaths(), brokenPath,candidateList.get(i).getFullpaths().size(),list.size());
												
						MyUtil.logging(fullpath.getSecond()+" "+brokenPath.getSecond());
						//System.out.println(fullpath.getSecond()+" "+brokenPath.getSecond());
						//now check which score is higher
						if(fullpath.getSecond()>=brokenPath.getSecond())
						{
							temp.setResult(fullpath.getFirst());
						}
						else
						{
							temp.setResult(brokenPath.getFirst());					
						}
						brokenPath=null;
					}
					else
					{
						temp.setResult(fullpath.getFirst());
					}
					
					temp.setToBeAlign(candidateList.get(i).getToBeAlign());
					fullpath=null;
					
					MyUtil.logging("Alignment String: "+temp.toString());
					//System.out.println("Alignment String: "+temp.toString());
					result.add(temp);
				}				
			}			
		}
	}
}
